1. Field of the Invention
The present invention relates generally to a communication system using Low-Density Parity-Check (LDPC) codes, and more particularly, to a channel decoding apparatus and method for decoding an LDPC code.
2. Description of the Related Art
LDPC codes are a subset of linear block codes. Although an LDPC code is generally defined by a party-check matrix, a bipartite graph, also known as a Tanner graph, can be used to represent the LDPC code. A bipartite graph is a graph whose nodes are divided into two sets, such that each node is connected to a node in the other set. The two sets of nodes on a Tanner graph are called variable nodes and check nodes. The variable nodes have a one-to-one correspondence to coded bits.
FIG. 1 illustrates a parity-check matrix H1 with four rows and eight columns representing an LDPC code. Referring to FIG. 1, the number of columns (8) defines the length of an LDPC codeword, and the columns represent the eight coded bits in the parity-check matrix H1.
FIG. 2 is a diagram illustrating a Tanner graph corresponding to the parity-check matrix H1 illustrated in FIG. 1.
Referring to FIG. 2, the Tanner graph representing the LDPC code includes eight variable nodes 202, 204, 206, 208, 210, 212, 214 and 216 (X1, X2, X3, X4, X5, X6, X7, X8) and four check nodes 218, 220, 222 and 224. An ith column and jth row in the parity-check matrix H1 represents a variable node Xi and a jth check node, respectively. If an entry at the ith column and jth row in the parity-check matrix H1 is one, i.e., non-zero, this means that an edge is drawn between the variable node Xi and the jth check node on the Tanner graph illustrated in FIG. 2.
The degree of a variable node or a check node on the Tanner graph of the LDPC code is the number of edges connected to the node. The degree of a node is equal to the number of non-zero entries in a column or row corresponding to the node in the parity-check matrix of the LDPC code. For example, the degrees of the variable nodes 202, 204, 206, 208, 210, 212, 214 and 216 (X1, X2, X3, X4, X5, X6, X7, X8) are 4, 3, 3, 3, 2, 2, 2 and 2, respectively. The degrees of the check nodes 218, 220, 222 and 224 are 6, 5, 5 and 5, respectively. Likewise, the numbers of non-zeroes in the columns of the parity-check matrix of FIG. 1, corresponding to the variable nodes of FIG. 2, are 4, 3, 3, 3, 2, 2, 2 and 2, respectively, and the numbers of non-zeroes in the rows of the parity-check matrix of FIG. 1, corresponding to the check nodes of FIG. 2, are 6, 5, 5 and 5.
The features of a parity-check matrix representing an LDPC code of a particular structure are described with reference to FIG. 3. The LDPC code of the structure illustrated in FIG. 3 has been adopted as a digital broadcasting standard in Europe.
Referring to FIG. 3, N1 denotes the length of an LDPC codeword, equal to the length of the parity-check matrix. K1 denotes the length of an information word, equal to the length of an information part in the parity-check matrix. (N1-K1) denotes the length of parity bits, equal to the length of a parity part in the parity-check matrix. Integers M1 and q are determined such that q=(N1−K1)/M1. Herein, K1/M1 is also an integer. For the sake of convenience, the parity-check matrix illustrated in FIG. 3 is referred to as a first parity-check matrix H1.
In the parity part of the parity-check matrix illustrated in FIG. 3, from a K1th column to an (N1−1)th column, the positions of weights preferably form, but are not limited to, a dual-diagonal structure. Therefore, the degrees of the columns in the parity part are all 2, except for the (N1−1)th column of degree 1.
The LDPC code of the above-described structure is generally represented by a parity-check matrix. Accordingly, efficient storage of information of the parity check matrix reduces a required memory size. If the LDPC code is stored in a conventional manner, a relatively large memory capacity is needed. In this context, many techniques have been studied to efficiently store the LDPC code.
For example, various Quasi-Cyclic LDPC (QC-LDPC) codes have been developed based on circulant permutation matrices in order to improve memory efficiency.
The QC-LDPC code may be represented by a parity-check matrix divided into small blocks. Each small block may be a circulant permutation matrix, the sum of two or more circulant permutation matrices, or a zero matrix. The QC-LDPC code is described in detail below with reference to FIG. 4.
FIG. 4 illustrates a parity-check matrix representing a typical QC-LDPC code. The parity-check matrix of the QC-LDPC code is divided into a plurality of partial blocks, each partial block being the sum of permutation matrices. The parity-check matrix illustrated in FIG. 4 includes m block rows and n block columns. An entry in an ith block row and a jth block column is the sum of permutation matrices. Notably, bij is 0 or a larger integer. In FIG. 4, reference character P denotes a permutation matrix having size NS×NS as shown in Equation (1). The superscript of P, ai,j(l) satisfies 0≦ai,j(l)≦NS−1.
Equation (1) is an example of the permutation matrix P illustrated in FIG. 4.
                    P        =                  [                                                    0                                            1                                            0                                                                                                                          0                                                                    0                                            0                                            1                                            …                                            0                                                                    ⋮                                            ⋮                                            ⋮                                                                                                                          ⋮                                                                    0                                            0                                            0                                            …                                            1                                                                    1                                            0                                            0                                            …                                            0                                              ]                                    (        1        )            
The above permutation matrix P is a square matrix of size NS×NS in which each of the NS rows has a weight 1 and each of the NS columns has a weight 1. Hereinafter, the size of the permutation matrix P, NS×NS is shortened as NS for convenience because the permutation matrix P is square.
If the superscript ai,j(l) of P is 0, the permutation matrix P0 is a unit matrix INS×NS. If bi,j is 0, the sum of permutation matrices P,
      ∑          l      =      1              b              i        ,        j              ⁢      P          a              i        ,        j                    (        l        )            is a zero matrix 0.
For an irregular LDPC code, information about the positions of all weights of a parity-check matrix representing the irregular LDPC code should be stored. Compared to an irregular LDPC code, only information about the positions of weights in the first column or row of each small block needs to be stored for a QC-LDPC code because once the positions of weights in the first column or row of each small block are determined, the positions of weights in the other columns or rows can be determined in the small block. As a consequence, about 1/NS of a memory capacity required for a general irregular LDPC code is sufficient for the QC-LDPC code. In other words, the QC-LDPC code outperforms the irregular LDPC code in terms of memory efficiency.
Layered decoding is a decoding scheme in which the rows of a parity-check matrix used for LDPC encoding and decoding are divided into a plurality of layers and the layers are iteratively decoded. A layer is defined as a group of rows divided from the parity-check matrix. Specifically, when the rows of the parity-check matrix are divided into a plurality of groups, each group is referred to as a layer. The layer may be one row. The layered decoding enables partial parallel decoding.
If the same position is accessed for two or more computations during the layered decoding, a memory collision may occur. To avert this problem, an additional memory or scheduling may be required.